namespace BinaryTree;

public class LC0108
{
    public TreeNode SortedArrayToBST(int[] nums)
    {
        return innerRecursive(nums, 0, nums.Length);
    }

    private TreeNode innerRecursive(int[] nums, int left, int right)
    {
        if (left == right) return null;
        if (left + 1 == right) return new TreeNode(nums[left]);

        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = innerRecursive(nums, left, mid);
        root.right = innerRecursive(nums, mid + 1, right);

        return root;
    }
}